package com.leetcode.offer.chapter4;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Dennis Li
 * @date 2020/7/13 20:15
 */
public class ValidateStackSequences_31 {

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new LinkedList<>();
        int k = 0;
        for (int i = 0; i < pushed.length; i++) {
            // 如果执行出栈时和辅助站栈顶的值相同，那么执行栈的出栈操作
            stack.push(pushed[i]);
            while (!stack.isEmpty() && stack.peek() == popped[k]) {
                stack.pop();
                k++;
            }
        }
        return stack.isEmpty();
    }

}
